package com.hanxiaozhang.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 〈一句话功能简述〉<br>
 * 〈二叉树相关题目〉
 *
 * @author hanxinghua
 * @create 2021/9/19
 * @since 1.0.0
 */
public class BinaryTreeTopic {

    /**
     * 举例：
     * ----------1
     * -------/    \
     * ------2      3
     * ----/  \   /  \
     * ---4    5 6    7
     * ------/  \    /
     * -----8   9   10
     *
     * @param args
     */
    public static void main(String[] args) {
        Node head = new Node(1);
        head.left = new Node(2);
        head.right = new Node(3);
        head.left.left = new Node(4);
        head.left.right = new Node(5);
        head.right.left = new Node(6);
        head.right.right = new Node(7);
        head.left.right.left = new Node(8);
        head.left.right.right = new Node(9);
        head.right.right.left = new Node(10);
        // 求最大层节点数
        System.out.println(topic1(head));
        System.out.println(topic2(head));
        System.out.println("----------");

    }

    /**
     * 求最大层节点数用Map
     * <p>
     * 前提，基于queue队列遍历二叉树每层数据
     *
     * @param head
     * @return
     */
    public static int topic1(Node head) {
        if (head == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        // Node在那一层
        HashMap<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, 1);
        // 当前你正在统计那一层
        int curLevel = 1;
        // 当前层，宽度目前是多少
        int curLevelNodes = 0;
        // 所有宽度最大值
        int max = 0;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int curNodeLevel = levelMap.get(cur);
            if (cur.left != null) {
                levelMap.put(cur.left, curNodeLevel + 1);
                queue.add(cur.left);
            }
            if (cur.right != null) {
                levelMap.put(cur.right, curNodeLevel + 1);
                queue.add(cur.right);
            }
            // 当前节点层数等于当前层，当前层的节点个数增加一
            if (curNodeLevel == curLevel) {
                curLevelNodes++;
            } else {
                // 统计最大值
                max = Math.max(max, curLevelNodes);
                // 当前层加一
                curLevel++;
                // 当前层个数设置为1
                curLevelNodes = 1;
            }
        }
        // 最后层，更最大值
        max = Math.max(max, curLevelNodes);
        return max;
    }

    /**
     * 求最大层节点数不用Map
     *
     * @param head
     * @return
     */
    public static int topic2(Node head) {
        if (head == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        // 当前层最右节点
        Node curEnd = head;
        // 下一层最右节点
        Node nextEnd = null;
        int max = 0;
        // 当前层节点数
        int curLevelNodes = 0;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                nextEnd = cur.left;
            }
            if (cur.right != null) {
                queue.add(cur.right);
                nextEnd = cur.right;
            }
            curLevelNodes++;
            // 当前节点是当前层的最右节点，证明当前层已经遍历完成，
            // 当前层节点个数已经统计完成
            if (cur == curEnd) {
                // 获取最大值
                max = Math.max(max, curLevelNodes);
                // 下一层，初始化数据
                curEnd = nextEnd;
                curLevelNodes = 0;
            }
        }
        return max;
    }


}
